/**
 * @file   main.cpp
 * @author Zhao jingting <jtzhao@Zhao jingting.
 * @date   The Nov 3 22:00:23 2021
 *
 * @brief  A program to test.
 *
 *
 */


#include"BinarySearchTree.h"
#include<vector>
#include<cstdlib>
#include<ctime>
#include <algorithm>
#include <random>
#include <chrono>
template<typename T>
void BST_sort(vector<T>& _data)
{
	BinarySearchTree<T> BST;
	int size = _data.size();
	for (int n = 0; n < size; n++)
	{
		BST.insert(_data[n]);
	}
	//inorder traversal
	BST.inorder();
	for (int n = 0; n < size; n++)
	{
		_data[n] = BST.s.front();
		BST.s.pop();
	}
	cout << "Number of calls to recursion: " << BST.count_settree << endl;
}


template<typename T>
int Randomize_BST_sort(vector<T>& _data)
{
	BinarySearchTree<T> BST;
	
	for (int n = 0; n < 20; n++)
	{
		int a = rand() % _data.size();
		int b = rand() % _data.size();
		while (a == b)
		{
			b = rand() % _data.size();
		}
		T c;
		c = _data[a];
		_data[a] = _data[b];
		_data[b] = c;
	}
	cout << "after randomizing: " ;
	for (int n = 0; n < 10; n++)
	{
		cout << _data[n] << " ";
	}
	cout << endl;
	int size = _data.size();
	for (int n = 0; n < size; n++)
	{
		BST.insert(_data[n]);
	}
	BST.inorder();
	for (int n = 0; n < size; n++)
	{
		_data[n] = BST.s.front();
		BST.s.pop();
	}
	cout << "Number of calls to recursion: " << BST.count_settree << endl;
	return BST.count_settree;
}

int main()
{
	srand(time(0));
	int averagetimes = 0;
	vector<int> v1;
	for (int n = 10; n > 0; n--)
	{
		v1.push_back(n);
	}
	cout << "the origin Vector: ";
	for (int n = 0; n < 10; n++)
	{
		cout << v1[n] << " ";
	}
	cout << endl;
	
	BST_sort(v1);
    cout << "after using BST_sort the  Vector: ";
	for (int n = 0; n < 10; n++)
	{
		cout << v1[n] << " ";
	}
	cout << endl<<endl << "-------------------------------------------------------------------------" << endl;
	for (int i = 0; i < 5; i++)
	{
		vector<int> v2;
		for (int n = 10; n > 0; n--)
		{
			v2.push_back(n);
		}
		cout << endl << endl << "the origin Vector: ";
		for (int n = 0; n < 10; n++)
		{
			cout << v2[n] << " ";
		}
		cout << endl;
		//calculate the efficiency
		averagetimes += Randomize_BST_sort(v2);
		cout << "after using Randomize_BST_sort the  Vector: ";
		for (int n = 0; n < 10; n++)
		{
			cout << v2[n] << " ";
		}
	}
	cout << endl << endl;
	cout << "the average Number of calls to recursion: " << double(averagetimes) / 5;
}
